|
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to describe the majority of current usage. ==Basics== A graph ''G'' consists of two types of elements, namely ''vertices'' and ''edges''. Every edge has two ''endpoints'' in the set of vertices, and is said to connect or join the two endpoints. An edge can thus be defined as a set of two vertices (or an ordered pair, in the case of a directed graph - see Section Direction). The two endpoints of an edge are also said to be adjacent to each other. Alternative models of graphs exist; e.g., a graph may be thought of as a Boolean binary function over the set of vertices or as a square (0,1)-matrix. A vertex is simply drawn as a ''node'' or a ''dot''. The vertex set of ''G'' is usually denoted by ''V''(''G''), or ''V'' when there is no danger of confusion. The order of a graph is the number of its vertices, i.e. |''V''(''G'')|. An edge (a set of two elements) is drawn as a ''line'' connecting two vertices, called endpoints or end vertices or endvertices. An edge with endvertices ''x'' and ''y'' is denoted by ''xy'' (without any symbol in between). The edge set of ''G'' is usually denoted by ''E''(''G''), or ''E'' when there is no danger of confusion. An edge ''xy'' is called incident to a vertex when this vertex is one of the endpoints ''x'' or ''y''. The size of a graph is the number of its edges, i.e. |''E''(''G'')|. A loop is an edge whose endpoints are the same vertex. A link has two distinct endvertices. An edge is multiple if there is another edge with the same endvertices; otherwise it is simple. The multiplicity of an edge is the number of multiple edges sharing the same end vertices; the multiplicity of a graph, the maximum multiplicity of its edges. A graph is a simple graph if it has no multiple edges or loops, a multigraph if it has multiple edges, but no loops, and a multigraph or pseudograph if it contains both multiple edges and loops (the literature is highly inconsistent). When stated without any qualification, a graph is usually assumed to be simple, except in the literature of category theory, where it refers to a quiver. Graphs whose edges or vertices have names or labels are known as labeled, those without as unlabeled. Graphs with labeled vertices only are vertex-labeled, those with labeled edges only are edge-labeled. The difference between a labeled and an unlabeled graph is that the latter has no specific set of vertices or edges; it is regarded as another way to look upon an isomorphism type of graphs. (Thus, this usage distinguishes between graphs with identifiable vertex or edge sets on the one hand, and isomorphism types or classes of graphs on the other.) (Graph labeling usually refers to the assignment of labels (usually natural numbers, usually distinct) to the edges and vertices of a graph, subject to certain rules depending on the situation. This should not be confused with a graph's merely having distinct labels or names on the vertices.) A hyperedge is an edge that is allowed to take on any number of vertices, possibly more than 2. A graph that allows any hyperedge is called a hypergraph. A simple graph can be considered a special case of the hypergraph, namely the 2-uniform hypergraph. However, when stated without any qualification, an edge is always assumed to consist of at most 2 vertices, and a graph is never confused with a hypergraph. A non-edge (or anti-edge) is an edge that is not present in the graph. More formally, for two vertices and , is a non-edge in a graph whenever is not an edge in . This means that there is either no edge between the two vertices or (for directed graphs) at most one of and from is an arc in G. Occasionally the term cotriangle or anti-triangle is used for a set of three vertices none of which are connected. The complement of a graph ''G'' is a graph with the same vertex set as ''G'' but with an edge set such that ''xy'' is an edge in if and only if ''xy'' is not an edge in ''G''. An edgeless graph or empty graph or null graph is a graph with zero or more vertices, but no edges. The empty graph or null graph may also be the graph with no vertices and no edges. If it is a graph with no edges and any number of vertices, it may be called the null graph on vertices. (There is no consistency at all in the literature.) A graph is infinite if it has infinitely many vertices or edges or both; otherwise the graph is finite. An infinite graph where every vertex has finite ''degree'' is called locally finite. When stated without any qualification, a graph is usually assumed to be finite. See also continuous graph. Two graphs ''G'' and ''H'' are said to be isomorphic, denoted by ''G'' ~ ''H'', if there is a one-to-one correspondence, called an isomorphism, between the vertices of the graph such that two vertices are adjacent in ''G'' if and only if their corresponding vertices are adjacent in ''H''. Likewise, a graph ''G'' is said to be homomorphic to a graph ''H'' if there is a mapping, called a homomorphism, from ''V''(''G'') to ''V''(''H'') such that if two vertices are adjacent in ''G'' then their corresponding vertices are adjacent in ''H''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Glossary of graph theory」の詳細全文を読む スポンサード リンク
|